package acm.蓝桥16;

import java.util.*;

public class C飞向城市 {
    /**
     * 一个无向带权图，问最短路
     */
    static int maxN = 1000;
    static int maxM = 10000;
    static int maxCN = 200;
    static int maxW = 1000;
    //long
    static int[] w;
    static List<Edge>[] nodes;
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        nodes = new List[n + 1];
        w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            nodes[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int v = sc.nextInt();
            nodes[from].add(new Edge(from, to, v));
            nodes[to].add(new Edge(to, from, v));
        }
        w[n]=0;
        long djs = djs(1, n);
        System.out.println(djs);
    }

    public static long djs(int s, int e) {
        long[] dis = new long[n + 1];
        Arrays.fill(dis,Long.MAX_VALUE);
        boolean[] vis = new boolean[n + 1];
        int cnt = 0;
        PriorityQueue<long[]> queue = new PriorityQueue<>((a, b) -> a[1] < b[1] ? -1 : 1);    //0位置id，1位置距离
        queue.add(new long[]{s, 0});
        dis[s]=0;
        while (!queue.isEmpty() && cnt < n) {
            long[] poll = queue.poll();
            int id = (int) poll[0];
            if (id==e) break;
            if (vis[id]) continue;
            long v = poll[1];
            cnt++;
            vis[id]=true;
            for (Edge edge : nodes[id]) {
                long d=edge.w+v+w[edge.to];
                if (d<dis[edge.to]){
                    dis[edge.to]=d;
                    queue.add(new long[]{edge.to,d});
                }
            }
        }
        return dis[e];
    }

    static class Edge {
        int from, to;
        int w;

        public Edge(int from, int to, int w) {
            this.from = from;
            this.to = to;
            this.w = w;
        }
    }
}
